package airthmetic.exercise.dp;

public class _1143_最长公共子序列 {
    public int longestCommonSubsequence(String text1, String text2) {
        /**
         1.确定状态参数/选择和决策
         状态参数是在子问题与原问题之间变化的值
         此题两个状态参数为: t1[1,i] t2[1,j]
         选择/决策 通过一个个子问题做选择改变状态参数的值，并逐步趋近于原问题
         此题是选择对应字符串的第几个元素
         2.定义dp数组(table 表)的含义
         原问题的解依赖于子问题，子问题需要缓存到dp数组内。
         int[][] dp = new int[n][m];
         此题为二维数组，int[n][m]表示当前位置对应的最长公共子序列的长度
         3.初始化dp数组
         子问题的初始状态
         此题为： n为0即空串时，与m任何一列都不能找到任何公共子序列 所以n=0时，此时为最长子序列为0；
         m为0即空串时，与n任何一行都不能找到任何公共子序列 所以m=0时，此时为最长子序列为0；

         for(int i=0; i<=n; i++){
         dp[i][0] = 0;
         }
         for(int j=0; j<=m; j++){
         dp[0][j] = 0;
         }
         4.推导状态转移逻辑(状态转移公式)
         即如何根据dp[0][0],dp[0][1],dp[1][1]...dp[i-1][j-1]的值推导出dp[i]dp[j]的值
         if(t1[i] == t2[j]){
         dp[i][j] = dp[i-1][j-1] + 1;
         }else{
         dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j])
         }
         */
        if(text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0){
            return 0;
        }
        char[] t1 = text1.toCharArray();
        char[] t2 = text2.toCharArray();
        int n = t1.length;
        int m = t2.length;
        // 定义dp数组和初始化
        int[][] dp = new int[n+1][m+1];
        for(int i=0; i<=n; i++){
            dp[i][0] = 0;
        }
        for(int j=0; j<=m; j++){
            dp[0][j] = 0;
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(t1[i-1] == t2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }

        return dp[n][m];
    }




    public static int longestCommonSubsequence2(String text1, String text2) {
        /**
         1.确定状态参数和选择
         状态参数： 状态参数是在原问题与子问题之间不断变化的值
         可以想想当前问题下，原问题与子问题是什么样子的
         原问题：text1 = "abcde" text2="ace"
         子问题：text1 = "abc" text"ac"
         所以此问题有两个状态参数：t1[1...i], t2[1...j]，注意			这里的i和j表示的是第几个元素非数组下标
         选择/决策: 通过做选择让状态参数不断变化， 并趋近于原问题的			解。
         此题的选择是：for循环数组元素的下标

         2.定义dp table的含义
         动态规划的思想是通过子问题推导原问题的解。子问题的解需要缓存起		   来。
         此题的dp表含义定义为：当前循环下t1与t2的字符串最长公共子序列		 长度
         int[][] dp = new int[][];

         3.初始化dp table
         根据题意，我们得知当t1等于空串时，不管t2多长，最长公共子序列		也只能是0。同理当t2等于空串时一致。
         所以我们初始化 dp第一列和第一行都是0。
         虽然Java中初始化的 int[][] dp = new int[][] 本身就都是0,为了语义化。还是做一下这个操作。

         4.推导状态转移公式
         动态规划的思想是根据子问题推导原问题的解。
         即知道dp[1][1]...dp[i-1][j-1]之后如何推导dp[i][j]
         此题根据题意:
         如果当前t1[i] == t2[j]字符一致，那么我们就在子问题的基			  础上+1。
         如果t1[i] != t2[j]字符不一致，我们分析得知，我们需要在			  dp[i][j-1] 或 dp[i-1][j]的基础上转移过来。

         if(t1[i] == t2[j]){
         dp[i][j] = dp[i-1][j-1] + 1;
         }else{
         dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
         }
         */

        char[] t1 = text1.toCharArray();
        char[] t2 = text2.toCharArray();
        int n = t1.length;
        int m = t2.length;
        int[][] dp = new int[n+1][m+1];
        for(int i=0; i<n; i++){
            dp[i][0] = 0;
        }
        for(int j=0; j<m; j++){
            dp[0][j] = 0;
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(t1[i-1] == t2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        return dp[n][m];
    }


    public static void main(String[] args) {
        String text1 = "abc";
        String text2 = "abc";
        System.out.println(longestCommonSubsequence2(text1, text2));
    }


    // 状态压缩
    public static int longestCommonSubsequence3(String text1, String text2) {
        /**
         因为问题具备重叠子问题和无后效性及最优子结构。动态规划！

         动态规划思考问题：
         什么是原问题什么是子问题
         原问题 t1[0...i] t2[0...j]
         子问题 t2[0...i-1] t2[0... j-1]
         子问题 t1[0...i-1] t2[0... j]
         子问题 t1[0...i] t2[0... j-1]

         1.确定状态参数和选择
         状态参数：在原问题与子问题之间不断变化的值
         此题两个状态分别为 t1 与 t2 的下标在不断变化

         选择/决策：做选择使状态参数不断变化并趋近于原问题的解
         选择下标

         2.定义dp table的含义
         int[][] dp = new int[t1.length + 1][t2.length + 1];
         dp[i][j]表示 字符串text1从0到i的子串  与text2从0到j的子串最长公共子序列长度

         3.初始化dp table
         当字符串t1等于空时与t2字符串最长公共子序列长度为0
         当字符串t2等于空时与t1字符串最长公共子序列长度为0

         4.推导状态转移公式
         for(int i=1; i<=t1.length; i++){
         for(int j=1; j<=t2.length; j++){
         if(t1[i-1] == t2[j-1]){
         dp[i][j] = dp[i-1][j-1] + 1;
         }else{
         dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
         }
         }
         }

         return dp[t1.length][t2.length];

         */

        char[] t1 = text1.toCharArray();
        char[] t2 = text2.toCharArray();
        int m = t1.length;
        int n = t2.length;
        int[] dp = new int[n+1];
        for(int i=1; i<=m; i++){
            int up = 0;
            for(int j=1; j<=n; j++){
                int leftUp = up;
                up = dp[j];
                if(t1[i-1] == t2[j-1]){
                    dp[j] = leftUp + 1;
                }else{
                    dp[j] = Math.max(dp[j-1], up);
                }
            }
        }

        return dp[n];


    }
}
